package com.simon.study.algorithm.review;

import java.util.Arrays;

/**
 * <p>
 *
 * @author simon
 * @date 2022/8/31 11:11 上午
 */
public class BucketSortDup {

    public static void main(String[] args) {
        int[] arr = new int[]{21, 5, 4, 1, 42, 83, 98, 6, 3, 4, 1};
        bucketSort(arr);

        System.out.println(Arrays.toString(arr));

        arr = new int[]{1, 3, 4, 9, 12, 23, 38, 45, 50, 54, 61};
        System.out.println(binarySearch(arr, 0, arr.length-1, 61));
        System.out.println(binarySearch(arr, 0, arr.length-1, 62));
        System.out.println(binarySearch(arr, 0, arr.length-1, 0));
        System.out.println(binarySearch(arr, 0, arr.length-1, 12));

        System.out.println(recursiveBsearch(arr, 0, arr.length-1, 62));
        System.out.println(recursiveBsearch(arr, 0, arr.length-1, 1));
        System.out.println(recursiveBsearch(arr, 0, arr.length-1, 45));
        System.out.println(recursiveBsearch(arr, 0, arr.length-1, 3));
        System.out.println(recursiveBsearch(arr, 0, arr.length-1, 4));
        System.out.println(recursiveBsearch(arr, 0, arr.length-1, 0));

        arr = new int[]{4, 12, 1, 61, 38, 3, 23, 54, 50, 45, 9};
        System.out.println(kthFind(arr, 0, arr.length-1, 7));
    }


    public static void bucketSort(int[] arr){
        int[] dup = new int[arr.length];

        int bs = getMaxbits(arr);

        for (int n = 1; n <= bs; n++) {
            int[] bucket = new int[10];

            for (int i = 0; i < arr.length; i++) {
                int dn = getBit(arr[i], n);
                bucket[dn]++;
            }

            for (int i = 1; i < bucket.length; i++) {
                bucket[i] = bucket[i] + bucket[i-1];
            }

            for (int i = arr.length; i > 0; i--) {
                int dn = getBit(arr[i-1], n);
                dup[--bucket[dn]] = arr[i-1];
            }

            for (int i = 0; i < dup.length; i++) { arr[i] = dup[i]; }
        }

    }

    public static int getMaxbits(int[] arr){
        int max = 0;
        for (int i = 1; i < arr.length; i++) {
            max = arr[i] > arr[max] ? i : max;
        }

        int res = 0; max = arr[max];
        while (max > 0){
            max /= 10;
            res++;
        }

        return res;
    }

    public static int getBit(int n, int i){
        return ((int)(n/Math.pow(10, i-1))) % 10;
    }


    public static int binarySearch(int[] arr, int as, int ae, int num){
        int lp = as, rp = ae, mid;
        while (lp <= rp){
            mid = lp + (rp-lp)/2;
            if(arr[mid] == num){ return mid; }
            else if(arr[mid] > num){ rp = mid - 1; }
            else{ lp = mid + 1; }
        }
        return -1;
    }


    public static int recursiveBsearch(int[] arr, int as, int ae, int num){
        if( as > ae){ return  -1; }

        int mid = as + (ae-as)/2;

        if(arr[mid] == num){ return mid; }
        else if(arr[mid] > num){ ae = mid - 1; }
        else{ as = mid + 1;  }

        return recursiveBsearch(arr, as, ae, num);
    }


    public static int kthFind(int[] arr, int as, int ae, int kth){
        if( as > ae ){ return -1; }

        int t  = as + ((int)(Math.random() * (ae-as)));
        int ps = partition(arr, as, ae, t);
        if(ps == kth){ return arr[kth]; }
        else if(ps >  kth){ return kthFind(arr, as, ps-1, kth); }
        else{ return kthFind(arr, ps+1, ae, kth); }
    }

    public static int partition(int[] arr, int as, int ae, int idx){
        int left = as, ap = as, right = ae, num = arr[idx];

        while (ap <= right){
            if(arr[ap] < num && left++ < ap++){ swap(arr, left-1, ap-1); }
            else if(arr[ap] == num){ ap++; }
            else if(arr[ap] >  num){ if(ap == right){ break; } swap(arr, ap, right--); }
        }
        return left;
    }

    public static void swap(int[] arr, int i, int j){
        if( i == j ){ return; }
        arr[i] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}
